The subject matter of the present invention pertains to computer systems, and more particularly, to a method and an apparatus for avoiding deadlock in a computer system with two or more protocol-controlled busses connected by a bus adapter, if units of different busses simultaneously start operation for which more than one bus is needed.
In a computer system, various processors and input/output units disposed within the computer system may require access to a common shared data bus at approximately the same time. However, the data bus can handle only one access at a time. Therefore, some mechanism is required for determining which unit and which processor may be granted access to the bus.
Various arbitration mechanisms have been used by computer systems. In an article entitled "Performance Analysis of High-Speed Digital Busses for Multiprocessing Systems" by W. L. Bain and S. R. Ahuja, Bell Laboratories, Murray Hill, N.J., several arbitration mechanisms are discussed. The article discusses, for example, the Static Priority Algorithm, the Fixed Time Slice Algorithm, Dynamic Priority Algorithms including the Least Recently Used Algorithm and the Rotating Daisy Chain Algorithm, and the First Come First Served Algorithm.
Most of the above-mentioned arbitration mechanisms are based on a fixed priority in descending order. None take account of the following special features: dual level input/output (I/O) requests for preventing I/O time-outs, a rotating selectively changeable highest priority at all I/O levels for preventing processor lock-outs, an instruction cache preemptive grant which saves one arbitration cycle, data cache in-page and cast-out operations in one cycle, which saves one arbitration cycle, and Processor Bus Operation (PBO) grants during refresh for utilizing cycles otherwise wasted.
U.S. Pat. No. 4,449,183 to Flahive et al discloses a mechanism for granting access to a shared bus on a "rotating priority basis". However, the arbitration scheme discussed in this patent resembles the rotating daisy chain algorithm mentioned above. There is no mention of the following special features and problems.
In a system with two data busses, where a bus unit of a bus #1 wants to communicate with a bus unit of a bus #2, while a bus unit of bus #2 wants to communicate with another bus unit of bus #1, the following deadlock situations may occur:
1. Both operations have been started and cannot be completed because the other bus is occupied.
2. No operation can be started.
The 1st situation will occur, if use of one bus is granted almost independently of the occupational state of the other bus.
The 2nd situation will occur, if use of a bus is granted only when the other bus is free.
According to the above-mentioned prior art, there are two known ways to solve the problem. Both adversely affect the performance of the system.
By the first method, a higher priority is assigned to one of the busses. An operation on the second bus can start only after both busses have activated their GRANT signals. Operations on the higher priority bus may start whenever this bus is free. This scheme requires several additional bus cycles for each operation started on the low-priority bus.
The second method allows all operations to start whenever their respective bus has issued its GRANT signal. However, whenever the bus coupling device receives two operations which are to be transferred to the other bus, it will cancel one operation. In this case, the cancelled operation has to be started anew after the operation which caused the cancellation has been completed. The performance penalty is only on the cancelled operation, but unduly frequent cancellation, say, in case of register polling, may prompt an operation never to be performed.
Accordingly, a general object of the present invention is to provide a method for avoiding a deadlock in a system with several busses interconnected by a bus adapter, which is universally applicable to a variety of different I/O device busses or adapters therefor.
Another general object of the present invention is to provide an apparatus which comprises less complicated adapters and avoids deadlock situations.